package problem;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class S_116 {

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val,Node _left,Node _right,Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    //1.层次遍历
    class Solution {
        public Node connect(Node root) {
            List<List<Node>> res=new ArrayList<>();
            if(root==null) return root;
            Queue<Node> queue=new LinkedList<>();
            queue.add(root);
            int level=0;
            while(!queue.isEmpty()){
                res.add(new ArrayList<>());
                int num=queue.size();
                for(int i=0;i<num;i++){
                    Node node=queue.remove();
                    res.get(level).add(node);
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                }
                level++;
            }
            for(int i=0;i<res.size();i++){
                for(int j=0;j<res.get(i).size();j++){
                    if(j==res.get(i).size()-1) break;
                    res.get(i).get(j).next=res.get(i).get(j+1);
                }
            }
            return root;
        }
    }

    //2.递归
    class Solution1{
        public Node connect(Node root){
            if(root==null) return root;
            if(root.left!=null){
                root.left.next=root.right;
                if(root.next!=null) root.right.next=root.next.left;
            }
            connect(root.left);
            connect(root.right);
            return root;
        }
    }

    //3.迭代
    class Solution2{
        public Node connect(Node root){
            Node pre=root;
            while(pre!=null){
                Node cur=pre;
                while(cur!=null){
                    if(cur.left!=null) cur.left.next=cur.right;
                    if(cur.right!=null&&cur.next!=null) cur.right.next=cur.next.left;
                }
                pre=pre.left;
            }
            return root;
        }
    }
}
